package com.lx.algorithm.mergeSort;

/**
 * Description: 归并排序
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: ������
 * @version: 1.0
 * Create at:   2021-09-02 23:07:41
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-09-02     张李鑫                     1.0         1.0 Version
 */
public class MargeSort {



    public static void sout(Integer a) {
        a += 2;
    }


    /**
     * <p>
     * 递归:一直找中间位置排序 做到2 2有序 然后合并 反推到递归开始的地方
     * </p>
     *
     * @param
     * @return int[]
     * @Author zlx
     * @date 2021/9/3
     */
    public int[] mergeSortByRecursion() {
        return null;
    }


    /**
     * <p>
     * 非递归: 保证步长内有序 然后合并步长
     * </p>
     *
     * @param
     * @return int[]
     * @Author zlx
     * @date 2021/9/3
     */
    public int[] mergeSort(int[] arr) {

        int mergeSize = 1;
        int right = arr.length;
        while (mergeSize < right) {
            int left = 0;
            while (left < right) {
                if (mergeSize >= right - left) {
                    break;
                }
                int mid = left + mergeSize - 1;
                int end = mid + Math.min(mergeSize, right - mid - 1);
                mergeArr(arr, left, mid, end);
                left = end + 1;
            }
            //防止越界
            if (mergeSize > right / 2) {
                break;
            }
            mergeSize <<= 1;
        }
        return arr;
    }


    /**
     * <p>
     *
     * </p>
     *
     * @param arr
     * @param index
     * @param end
     * @return int[]
     * @Author zlx
     * @date 2021/9/3
     */
    public static int[] mergeArr(int[] arr, int index, int mid, int end) {
        int[] mergeArr = new int[end - index + 1];
        int i = 0;
        int left = index;
        int right = mid + 1;
        //同时遍历两个数组 往合并数组里加值 直到有一个数组越界
        while (left <= mid && right <= end) {
            mergeArr[i++] = arr[left] <= arr[right] ? arr[left++] : arr[right++];
        }
        //把没有越界的数组向合并数组里拼装
        while (left <= mid) {
            mergeArr[i++] = arr[left++];
        }
        while (right <= end) {
            mergeArr[i++] = arr[right++];
        }
        //合并
        for (int i1 = 0; i1 < mergeArr.length; i1++) {
            arr[index++] = mergeArr[i1];
        }
        return arr;
    }

    /**
     * <p>
     * 递归实现归并排序
     * </p>
     *
     * @param arr
     * @param L
     * @param R
     * @return void
     * @Author zlx
     * @date 2021/9/3
     */
    public static void process(int[] arr, int L, int R) {
        //确定出口
        if (L == R) {
            return;
        }
        int mid = L + ((R - L) >> 1);
        process(arr, L, mid);
        process(arr, mid + 1, R);
        mergeArr(arr, L, mid, R);
    }
    /**
     * todo:还有额外的附加题没左后续做
     * @param args
     */
    public static void main(String[] args) {
        //2+4+2+4+2+3+65+2+3+4 累加左边最小
        //3*4+2*4+65*1+2*3 累加右边有几个大于当前指针的数 91
        int [] arr=new int[]{4,2,65,3,245,23};
        process(arr,0,arr.length-1);
        System.out.println(123);
    }

}